package hot;

/**
 * @author lakersUp
 * @Classname   排序链表
 * @Description     归并排序
 * @Date 2022/3/13 9:52
 * @Version 1.0
 */
public class Hot148sortList {
    // 自顶向下的归并排序
    public ListNode sortList(ListNode head) {
        return sortList(head,null);
    }

    public ListNode sortList(ListNode head,ListNode tail){
        if(head==null){
            return head;
        }

        //细节!!!!!!!!!!
        if(head.next==tail) {
            head.next=null;
            return head;
        }

        ListNode slow=head;
        ListNode fast=head;
        while(fast!=tail){
            slow=slow.next;
            fast=fast.next;
            if(fast!=null){
                fast=fast.next;
            }
        }
        ListNode mid=slow;
        ListNode list1 = sortList(head, mid);
        ListNode list2 = sortList(mid,tail);
        return merge(list1,list2);
    }

    private ListNode merge(ListNode list1, ListNode list2) {
        ListNode dummyNode= new ListNode(-1);
        ListNode head=dummyNode;
        while (list1!=null && list2!=null){
            if(list1.val<=list2.val){
                head.next=list1;
                list1=list1.next;
            }else {
                head.next=list2;
                list2=list2.next;
            }
            head=head.next;
        }
        if(list1==null){
            head.next=list2;
        }
        if(list2==null){
            head.next=list1;
        }
        return dummyNode.next;
    }
}
